﻿#define _CRT_SECURE_NO_WARNINGS 1

int* findDisappearedNumbers(int* nums, int numsSize, int* returnSize)
{
    int* arr = (int*)malloc(sizeof(int) * numsSize);
    if (arr == NULL)
    {
        perror("malloc fail");
        exit(1);
    }
    *returnSize = 0;
    for (int i = 0; i < numsSize; ++i)
    {
        int x = (nums[i] - 1) % numsSize;//nums[] = {4,3,2,7,8,2,3,1,}; nums[0] - 1 = 3; nums[3] += numsSize; nums[] = {4,3,2,15,8,2,3,1,}; 15要取模，不然越界，类似这样的加下去还有很多
        nums[x] += numsSize;
    }

    for (int i = 0; i < numsSize; ++i)
    {
        if (nums[i] <= numsSize)
        {
            arr[(*returnSize)++] = i + 1;
        }
    }

    return arr;
}

/*
给你一个含 n 个整数的数组 nums ，其中 nums[i] 在区间 [1, n] 内。请你找出所有在 [1, n] 范围内但没有出现在 nums 中的数字，并以数组的形式返回结果。

示例 1：
输入：nums = [4,3,2,7,8,2,3,1]
输出：[5,6]

示例 2：
输入：nums = [1,1]
输出：[2]

链接：https://leetcode.cn/problems/find-all-numbers-disappeared-in-an-array



题解:
具体来说，遍历nums，每遇到一个数x,nums[x−1] 增加n。由于nums 中所有数均在[1,n] 中，
增加以后，这些数必然大于n。最后我们遍历numsnums，若nums[i] 未大于n，就说明没有遇到过数
i+1。这样我们就找到了缺失的数字。

注意，当我们遍历到某个位置时，其中的数可能已经被增加过，因此需要对n取模来还原出它本来的值。

*/




